
#include <stdio.h>
#include <stdlib.h>

struct res
{
	int n;
	int sum;
};
struct res arr[1024] = {0};
int main()
{
	int i = 0;
    int sum = 0;
    int n  = 10;
#if 1
	while(1)
    {
		printf("请输入n值： ");
        scanf("%d", &n);
        /*判断n对应的累加和是否计算过*/
        int j = 0;
        for(j=0; j<1024; j++)
        {
			if(arr[j].n == n)
            {
				sum = arr[j].sum;
				printf("查询得到： ");
				break;
            }
		}
		/*算法一*/
        if(j == 1024)
        {
    		for(i=0; i<=n; i++)
    		{
				sum += i;  //O(n)
			}
            /*找到未被使用的位置*/
            int m = 0;
            for(m=0; m<1024; m++)
			{
				if(arr[m].n == 0)
                {
					/*找到空位置*/
					break;
				}
			}
            arr[m].n = n;
            arr[m].sum = sum;
			printf("计算得到： ");
         }
		printf("sum = %d\n", sum);
	}
#endif
#if 0
	/*算法二*/
    sum = (1 + n) * (n/2); //O(1)
#endif
	return 0;
}



